/*
 * @Author: 缄默
 * @Date: 2022-03-09 20:00:52
 * @LastEditors: 缄默
 * @LastEditTime: 2022-03-10 19:32:55
 */

//N皇后问题

#include <iostream>
#include <vector>

using namespace std;

int num1(int n);
int process1(int i, vector<int>& record, int n);
bool isValid(vector<int>& record, int i, int j);


//位运算加速递归
int num2(int n);
int process2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim);
int main() {
    int n;
    cin >> n;
    cout << num1(n) << endl;
    cout << endl;
    cout << num2(n) << endl;

    cout << (~n) << endl;
    return 0;
}

int num1(int n) {
    if (n < 1) return 0;
    vector<int> record(n, 0);
    return process1(0, record, n);
}

int process1(int i, vector<int>& record, int n) {
    if (i == n) {
        return 1;
    }
    int res = 0;
    //判断i可在的位置
    for (int j = 0; j < n; j++) {
        if (isValid(record, i, j)) {
            record[i] = j;
            //i +  1可在位置的判断 类似于一种遍历
            res += process1(i + 1, record, n);
        }
    }
    return res;
}

bool isValid(vector<int>& record, int i, int j) {
    for (int k  = 0; k < i; k++) {
        if (j == record[k] || abs(record[k] - j) == abs(i - k)) {
            return false;
        }
    }
    return true;
}

int num2(int n) {
    if (n < 1 || n > 32) {
        return 0;
    }
    //1向左移n位并-1
    int upperLim = n == 32 ? -1 : (1 << n) - 1;
    return process2(upperLim, 0, 0, 0);
}

//upperLim 当前行哪些位置可以放置皇后
//colLim 递归计算到上一行为止，哪些位置已经放置皇后 1代表已经放置
//leftDiaLim 之前皇后对左下方影响导致左下方斜线处不能放置皇后的位置 1代表不能放置
//rightDiaLim 之前皇后对右下方位置影响 导致当前行不能放皇后的位置
//pos 当前行在colLim leftDiaLim rightDiaLim的影响下那些位置可以放置皇后 1代表可以放置
//mostRightOne pos中最右边的1的位置

int process2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim) {
    if (colLim == upperLim) {
        return 1;
    }
    int pos = 0;
    int mostRightOne = 0;
    pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
    int res = 0;
    while (pos != 0) {
        //找到pos中最右侧1的位置（为什么不是左侧？应为n的大小有限，均是从右侧开始的）
        //这个只能发现一位，但是他是逐位去除的
        mostRightOne = pos & (~pos + 1);
        //pos除去这个位置
        pos = pos - mostRightOne;
        res += process2(upperLim, colLim | mostRightOne, (leftDiaLim | mostRightOne) << 1, (rightDiaLim | mostRightOne) >> 1);
    }
    return res;

}